package LinkTest;
import java.util.LinkedHashSet;
import java.util.Set;

//前后指针法把链表变为奇偶重排
public class OddEvenSort {
    static class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
      this.val = val;
    }
 }
    public static ListNode oddEvenList (ListNode head) {
        // write code here
        if(head==null ||head.next==null){
            return head;
        }
        ListNode e=head.next;
        ListNode o=head;
        ListNode n=e;//保留偶头便于链接
        while(e!=null&&e.next!=null){//当至少还有两个节点一偶一奇时才继续执行
            o.next=e.next;//奇的下一个为偶的下一个
            o=o.next;//奇移到下一个
            e.next=o.next;//偶的下一个为奇的下一个
            e=e.next;//偶移到下一个
        }
        o.next=n;
        return head;
    }
    //去掉链表中重复的元素
    public static ListNode deleteDuplicates (ListNode head) {
        // write code here
        if(head==null || head.next==null){
            return head;
        }
        Set<Integer> set=new LinkedHashSet<Integer>();//LinkedHashSet是HashSet的子类，保证插入元素唯一且保持插入顺序
        ListNode cur=head;
        while(cur!=null){
                set.add(cur.val);//LinkedSet会去重存储且保持顺序

            cur=cur.next;
        }
        ListNode cur2=new ListNode(0);
        ListNode cur3=cur2;
        Integer[] arr=set.toArray(new Integer[0]);
        for(int val:arr){
            ListNode cur4=new ListNode(val);
            cur3.next=cur4;
            cur3=cur3.next;
        }
        return cur2.next;
    }
    import java.util.*;
    public class Solution {
        public ListNode deleteDuplicates (ListNode head) {
            //空链表
            if(head == null)
                return null;
            ListNode res = new ListNode(0);
            //在链表前加一个表头
            res.next = head;
            ListNode cur = res;
            while(cur.next != null && cur.next.next != null){
                //遇到相邻两个节点值相同
                if(cur.next.val == cur.next.next.val){
                    int temp = cur.next.val;
                    //将所有相同的都跳过
                    while (cur.next != null && cur.next.val == temp)
                        cur.next = cur.next.next;
                }
                else
                    cur = cur.next;
            }
            //返回时去掉表头
            return res.next;
        }
    }

        public static ListNode deleteDuplicates3 (ListNode head) {
            //空链表
            if(head == null)
                return null;
            ListNode res = new ListNode(0);
            //在链表前加一个表头
            res.next = head;
            ListNode cur = res;
            while(cur.next != null && cur.next.next != null){
                //遇到相邻两个节点值相同
                if(cur.next.val == cur.next.next.val){
                    int temp = cur.next.val;
                    //将所有相同的都跳过
                    while (cur.next != null && cur.next.val == temp)
                        cur.next = cur.next.next;
                }
                else
                    cur = cur.next;
            }
            //返回时去掉表头
            return res.next;
        }


}
